Planning

Travelling Sales Person

Recipe

Recipe - solving composition tasks

Composition tasks are problems where several ingredients are mixed together to produce a recipe. The constraints on the selection of the ingredients are normally the cost of materials and the resulting characteristics of the recipe.

As an example, consider an iron foundry producing grey iron. The quality of the iron produced must have a certain chemical analysis in order to achieve the physical properties required (tensile strength, hardness etc.). As the foundry might produce hundreds of tons daily, it is therefore essential to arrive at a composition of the available ingredients that will meet the chemical properties at the lowest possible cost.

The ingredients are Steel scrap, Pig Iron, Graphite, Ferro Silicon, Ferro Manganese and Return scrap. The chemical analysis required is Carbon (C) between 3.3-3.45%, Silicon (Si) between 2.1 - 2.3% and Manganese between 0.6-0.7%. The ingredients contain these elements in various proportions. Furthermore, there are upper and lower limits on the percentages allowed for each ingredient. The limits, proportions and the prices of the ingredients are shown below:

The sample application Recipe is an implementation of the above problem. Observe the chromosome definition by viewing the optimisation object RecipeOpt. The optimization structure consists of one non sequenced chromosome with six genes corresponding to the percentages of the ingredients. The chromosome has a sum constraint requiring that the sum of all percentages should add up to 100. Each gene is of type real (2 decimal places), tied to an attribute and with the minimum and maximum values defined in the above table. The @commands of Mix_Cost_PRC_VB calculate the resulting percentages of Carbon, Silicon and Manganese for a particular gene (mix of ingredients). The value of Mix_Cost contains contributions from two components:

(i)The actual Dollar cost of the ingredients.

(ii)A penalty for Carbon, Silicon and Manganese not being within the acceptable limits. This is calculated as 5000 units for every 1% deviation.

In this case, it is difficult to assign monetary penalty figures to the last component of the Mix_Cost. The choice of 5000 per 1% as a penalty for deviations from acceptable percentages is dictated by an understanding of how drastic is a deviation from limits. If it was absolutely unacceptable then we may set the penalty to 20000 per 1%. The evolution process is driven by the factors which influence Mix_Cost most. Hence, the initial generations will attempt to produce solutions with minimal deviation from acceptable limits in order to reduce these components of the cost. It is only then that the later generations will attempt to minimise the actual cost of the ingredients used.

When you Run the RECIPE task with the default evolution parameters, it should give a good solution of 1300-1500 dollars within ten generations. The optimal solution to the problem is about 1255 dollars.

RECIPE Script Commands:

You can examine the use of these specific Knowledge Builder procedural @commands used, by looking in these Procedure objects within the application.